package com.frx.sort.quicksort;

import java.util.Arrays;

/**
 * Created with IDEA
 *
 * @author: xrf
 * @Date: 2019/10/22
 * @Time: 15:07
 */
public class TestOne {

    public static void main(String[] args){
        int[] arr = {3,5,6,4,2,1};
        int[] arr1 = {7,5,6,4,2,3};
        quickSort(arr,0,arr.length-1);
        quickSort(arr1,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arr1));
    }

    public static void quickSort(int[] arr,int start,int end){

        if (start >= end){
            return;
        }
        int partition = partition(arr,start,end);
        quickSort(arr,start,partition-1);
        quickSort(arr,partition+1,end);
    }

    public static int partition(int[] arr,int left,int right){
        int pivot = left;
        while (left != right){
            while (left < right && arr[right] > arr[pivot]){
                right--;
            }
            while (left < right && arr[left] <= arr[pivot]){
                left++;
            }
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
        }
        int tmp = arr[pivot];
        arr[pivot] = arr[left];
        arr[left] = tmp;
        return left;
    }

}
